//
// Created by liushuai on 18-8-26.
//

#include "CMap.hpp"
#include <iostream>
#include <vector>
#include <memory.h>
CMap::CMap(int capacity) {
    Capacity = capacity;
    NodeCount = 0;
    NodeArray = new Node[Capacity];
    adj_Matrix = new int[Capacity*Capacity];
    memset(adj_Matrix,0,Capacity*Capacity* sizeof(int));
    pEdge = new Edge[Capacity-1];

}

CMap::~CMap() {
    delete [] NodeArray;
    delete [] adj_Matrix;
    delete [] pEdge;
}
bool CMap::addNode(Node *pNode) {
    if(pNode == nullptr)
        return false;
    NodeArray[NodeCount].m_cData = pNode->m_cData;
    NodeCount++;
    return true;
}
void CMap::resetNode() {
    for(int i=1;i<NodeCount;i++)
        NodeArray[i].m_bIsVisited = false;
}
bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val) {
    if(row<0||row>=Capacity)
        return  false;
    else if(col<0&&col>=Capacity)
        return false;
    else
    {
        NodeArray[row*Capacity+col] = val;
        return true;
    }

}
bool CMap::setValueToMatrixUndirectedGraph(int row, int col, int val) {
    if(row<0||row>=Capacity)
        return  false;
    else if(col<0&&col>=Capacity)
        return false;
    else
    {
        adj_Matrix[row*Capacity+col] = val;
        adj_Matrix[col*Capacity+row] = val;
        return true;
    }

}
void CMap::printMatrix() {
    for(int i=0;i<Capacity;i++)
    {
        for(int k=0;k<Capacity;k++)
        {
            std::cout<<adj_Matrix[i*Capacity+k]<<" ";
        }
        std::cout<<"\n";
    }
}
bool CMap::getValueFromMatrix(int row, int col, int &val) {
    if(row<0||row>=Capacity)
        return  false;
    else if(col<0&&col>=Capacity)
        return false;
    else
    {
        val = adj_Matrix[row*Capacity+col];
        return true;
    }
}
void CMap::DFS(int nodeIndex) {
    int value = 0;
    std::cout<<NodeArray[nodeIndex].m_cData<<" ";
    NodeArray[nodeIndex].m_bIsVisited = true;
    for(int i = 0;i<Capacity;i++)
    {
        getValueFromMatrix(nodeIndex,i,value);
        if(value == 1)
        {
            if(NodeArray[i].m_bIsVisited)
                continue;
            else
                DFS(i);
        }
        else
        {
            continue;
        }
    }
}
void CMap::BFS(int nodeIndex) {
    std::cout<<NodeArray[nodeIndex].m_cData<<" ";
    NodeArray[nodeIndex].m_bIsVisited = true;
    std::vector<int> cuVec;
    cuVec.push_back(nodeIndex);
    breadthFirstTraverseImp(cuVec);
}
void CMap::breadthFirstTraverseImp(std::vector<int> preVec) {
    int value = 0;
    std::vector<int> curVec;
    for(int j=0;j<(int)preVec.size();j++)
    {
        for(int i=0;i<Capacity;i++)
        {
            getValueFromMatrix(preVec[j],i,value);
            if(value!=0)
            {
                if(NodeArray[i].m_bIsVisited)
                    continue;
                else
                {
                    std::cout<<NodeArray[i].m_cData<<" ";
                    NodeArray[i].m_bIsVisited = true;
                    curVec.push_back(i);
                }
            }

        }

    }
    if(curVec.size() == 0)
        return;
    else
        breadthFirstTraverseImp(curVec);
}
void CMap::primTree(int nodeIndex) {
    int value = 0;
    int edgeCount = 0;
    std::vector<int> nodeVec;
    std::vector<Edge> edgeVec;
    std::cout<<NodeArray[nodeIndex].m_cData<<"\n";
    nodeVec.push_back(nodeIndex);
    NodeArray[nodeIndex].m_bIsVisited = true;
    while (edgeCount<Capacity-1)
    {
        int temp = nodeVec.back();
        for(int i=0;i<Capacity;i++)
        {
            getValueFromMatrix(temp,i,value);
            if(value != 0)
            {
                if(NodeArray[i].m_bIsVisited)
                    continue;
                else
                {
                    Edge edge(temp,i,value);
                    edgeVec.push_back(edge);
                }
            }
        }
        // 从可选边集合中找到最小边
        int edgeIndex = getMinEdge(edgeVec);
        edgeVec[edgeIndex].Selected = true;
        std::cout<<edgeVec[edgeIndex].NodeIndexA
                 <<" ----- "<<edgeVec[edgeIndex].NodeIndexB
                 <<"\t"<<edgeVec[edgeIndex].WeightValue<<"\n";
        pEdge[edgeCount] = edgeVec[edgeIndex];
        edgeCount++;
        int nextNodeINdex = edgeVec[edgeIndex].NodeIndexB;
        nodeVec.push_back(nextNodeINdex);
        NodeArray[nextNodeINdex].m_bIsVisited = true;
        std::cout<<NodeArray[nextNodeINdex].m_cData<<"\n";

    }
}
bool CMap::isInSet(std::vector<int> &nodeSet, int target) {
    for(int i=0;i<nodeSet.size();i++)
    {
        if(nodeSet[i] == target)
            return true;
    }
    return false;
}
void CMap::mergeNodeSet(std::vector<int> &nodeSetA, std::vector<int> nodeSetB) {
    for(int i=0;i<nodeSetB.size();i++)
        nodeSetA.push_back(nodeSetB[i]);
}
int CMap::getMinEdge(std::vector<Edge> edgeVec) {
    int minWeight = 0;
    int edgeIndex = 0;
    int i;
    for(i=0;i<edgeVec.size();i++)
    {
        if(!edgeVec[i].Selected)
        {
            minWeight = edgeVec[i].WeightValue;
            edgeIndex = i;
            break;
        }
    }
    if(minWeight == 0)
        return -1;
    for(;i<edgeVec.size();i++)
    {
        if(edgeVec[i].Selected)
            continue;
        else
        {
            if(minWeight>edgeVec[i].WeightValue)
            {
                minWeight = edgeVec[i].WeightValue;
                edgeIndex = i;
            }
        }
    }
    return edgeIndex;
}
void CMap::kruskalTree() {
    int value = 0;
    int edgeCount = 0;
    std::vector<std::vector<int>> nodeSets;
    std::vector<Edge> edgeVec;
    for(int i=0;i<Capacity;i++)
    {
        for(int k=i+1;k<Capacity;k++)
        {
            getValueFromMatrix(i,k,value);
            if(value!=0)
            {
                Edge edge(i,k,value);
                edgeVec.push_back(edge);
            }
        }
    }
    while(edgeCount<Capacity-1)
    {
        int minEdgeIndex = getMinEdge(edgeVec);
        edgeVec[minEdgeIndex].Selected = true;
        int NodeAIndex = edgeVec[minEdgeIndex].NodeIndexA;
        int NodeBIndex = edgeVec[minEdgeIndex].NodeIndexB;

        bool nodeAIsInSet = false;
        bool nodeBIsInSet = false;
        int nodeAInSetLabel = -1;
        int nodeBInSetLabel = -1;
        for(int i=0;i<nodeSets.size();i++)
        {
            nodeAIsInSet = isInSet(nodeSets[i],NodeAIndex);
            if(nodeAIsInSet)
                nodeAInSetLabel = i;
        }
        for(int j=0;j<nodeSets.size();j++)
        {
            nodeBIsInSet = isInSet(nodeSets[j],NodeBIndex);
            if(nodeBIsInSet)
                nodeBInSetLabel = j;
        }
        if(nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
        {
            std::vector<int> vec;
            vec.push_back(NodeAIndex);
            vec.push_back(NodeBIndex);
        }
        else if(nodeAInSetLabel != -1&&nodeBInSetLabel == -1)
        {
            nodeSets[nodeAInSetLabel].push_back(NodeBIndex);
        }
        else if(nodeAInSetLabel!=-1&&nodeBInSetLabel!=-1&&nodeAInSetLabel!=nodeBInSetLabel)
        {
            mergeNodeSet(nodeSets[nodeAInSetLabel],nodeSets[nodeBInSetLabel]);
            for(int k=nodeBInSetLabel;k<nodeSets.size()-1;k++)
                nodeSets[k] = nodeSets[k+1];
        }
        else if(nodeAInSetLabel!=-1&&nodeBInSetLabel!=-1&&nodeAInSetLabel == nodeBInSetLabel)
            continue;
        pEdge[edgeCount] = edgeVec[minEdgeIndex];
        edgeCount++;
        std::cout<<edgeVec[minEdgeIndex].NodeIndexA<<"---"
                                                     <<edgeVec[minEdgeIndex].NodeIndexB<<" ";
        std::cout<<edgeVec[minEdgeIndex].WeightValue<<"\n";
    }
}


















